package org.zhangyp.n03algorithm.n03Sort;

import java.util.Arrays;

/**
 * 选择&冒泡&快速
 *
 * @author ypzhang
 * @since 2024/12/25
 */
public class BSort {

    /**
     * 选择排序
     * 选择排序和插入排序比较像，也有两个区域，无序区域和有序区域，不同的是，每次都从无序区域中找出最小的值插入到有序区域的末尾，
     *
     * @param data
     */
    public static <T extends Number> void selectSort(T[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j].doubleValue() < data[minIndex].doubleValue()) {
                    minIndex = j;
                }
            }
            // 交换位置
            T min = data[minIndex];
            data[minIndex] = data[i];
            data[i] = min;
        }
    }


    /**
     * 冒泡排序
     * 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
     * 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作
     *
     * @param data
     */
    public static <T extends Number> void bubbleSort(T[] data) {
        for (int end = data.length - 1; end > 0; end--) {
            // 排一次之后就可以少比较一个数
            for (int i = 0; i < end; i++) {
                if (data[i].doubleValue() > data[i + 1].doubleValue()) {
                    // 交换位置
                    T tmp = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = tmp;
                }
            }
        }
    }

    /**
     * 快速排序
     *
     * @param data
     */
    public static <T extends Number> void quiklySort(T[] data) {
        quiklySort(data, 0, data.length - 1);
    }

    public static <T extends Number> void quiklySort(T[] data, int start, int end) {
        int left = start;
        int right = end;
        while (left < right) {
            //从右边往左边数，找比基准数小的，左边与之交换，此时基准数在左边
            while (left < right && data[right].doubleValue() >= data[left].doubleValue()) {
                right--;
            }
            if (left < right) { // 找到一个比基准数小的数，与左边交换位置
                T temp = data[right];
                data[right] = data[left];
                data[left] = temp;
                // 此时基准数到了右边，刚交换的数在左边left位置上，不必再比较，所以left后移一个位置
                left++;
            }
            // 从左边往右数，找比基准数大的数，右边与之交换，此时基准数在右边
            while (left < right && data[left].doubleValue() <= data[right].doubleValue()) {
                left++;
            }
            // 找到了一个比基准数大的数，与右边交换
            if (left < right) {
                T temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                // 此时基准数又到了左边，刚交换的数在右边right位置上，不必再比较，所以right前移一个位置
                right--;
            }
        }
        // 最终left = right
        if (left > start) {
            quiklySort(data, start, left - 1);
        }

        if (left < end) {
            quiklySort(data, left + 1, end);
        }
    }

    public static void main(String[] args) {
        Integer[] data = {9, 3, 4, 6, 1, 2, 7, 5, 0, 8};
        quiklySort(data);
        System.out.println(Arrays.toString(data));

    }
}
